package dipl.algorithm.math.geometry.op;

import dipl.algorithm.exception.ArgumentNullException;
import dipl.algorithm.math.primitive.Point2d;
import dipl.algorithm.math.primitive.op.Point2dOps;

/**
 * Class provides operators on 2d point sets.
 */
public  class Point2dSetOps {

	//
	// PUBLIC METHODS
	//

	/**
	 * Calculates convex hull of given points using Graham's scan and
	 * returns copies of the points belonging to hull in clockwise order.
	 * Running time: O(nlogn)
	 * param pointset array of points
	 * param hullSet resulting hull (<code>null</code> if number of points = 0)
	 * param leaveInputUnchanged
	 *   Whether or not to leave input array unchanged.
	 *   If <code>false</code> the ordering of points in the input array may be changed.
	 */
	public static Point2d[] ComputeConvexHull( Point2d[] pointSet, boolean leaveInputUnchanged ) {
		return ComputeConvexHull( pointSet, pointSet.length, leaveInputUnchanged );
	}

	/**
	 * Calculates convex hull of given points using Graham's scan and
	 * returns copies of the points belonging to hull in clockwise order.
	 * Running time: O(nlogn)
	 * param pointset array of points
	 * param numPoints number of points in array (may be less than length of array)
	 * param hullSet resulting hull (<code>null</code> if number of points = 0)
	 * param leaveInputUnchanged
	 *   Whether or not to leave input array unchanged.
	 *   If <code>false</code> the ordering of points in the input array may be changed.
	 */
	public static Point2d[] ComputeConvexHull( Point2d[] pointSet, int numPoints, boolean leaveInputUnchanged ) {
		// check out some nasty cases
		if( numPoints == 0 ) // no points -> no hull
			return null;

		Point2d[] hullSet = null; // resulting hull points
	
		int i; // indices
		int n = numPoints; // number of points

		if( leaveInputUnchanged ) { // create copy of input
			hullSet = new Point2d[numPoints];
			for( i = 0; i < n; i++ ) {
				hullSet[i] = pointSet[i];
			}
		}
		else {
			hullSet = pointSet;
		}

		if( n == 1 )
			return hullSet;

		// sort points lexicographically first
		SortPointsLexicographically( hullSet, numPoints );


		Point2d[] hull = new Point2d[n*2]; // hull calculated so far
		int index; // size of hull so far

		// construct upper hull

		hull[0] = hullSet[0];
		hull[1] = hullSet[1];
		index = 1;
		for( i = 2; i < n; i++ ) {
			index++;
			hull[index] = hullSet[i];
			while( index > 1 && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}

		int upperHullSize = index+1; // hull size at this moment

		// construct lower hull
		index++;
		hull[index] = hullSet[n-2];

		for( i = n-3; i >= 0; i-- ) {
			index++;
			hull[index] = hullSet[i];
			while( index > upperHullSize && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}
		index--; // last point is twice in list (first and last)

		// fill hullset with hull points
		hullSet = new Point2d[index+1];
		for( i = 0; i <= index; i++ ) {
			hullSet[i] = hull[i];
		}
		return hullSet;
	}

	/**
	 * Returns whether given two point-sets are equal.
	 * @param ps_a
	 * @param ps_b
	 * @return
	 * @throws ArgumentNullException one argument is null
	 */
	public static boolean AreEqual( Point2d[] ps_a, Point2d[] ps_b ) throws Exception {
		if( ps_a == null || ps_b == null )
			throw new ArgumentNullException();

		if( ps_a.length != ps_b.length )
			return false;

		int i;
		for( i = 0; i < ps_a.length; i++ ) {
			if( ps_a[i].x.compareTo( ps_b[i].x ) != 0 || ps_a[i].y.compareTo( ps_b[i].y ) != 0 )
				return false;
		}
		return true;
	}

	/**
	 * Returns ab, the array formed by concatenating a and b
	 * @param a
	 * @param b
	 * @return
	 */
	public static Point2d[] Concat( Point2d[] a, Point2d[] b ) {
		int n = a.length;
		int l = n+b.length;
		Point2d[] res = new Point2d[l];
		for( int i = 0; i < n; i++ ) {
			res[i] = a[i];
		}
		int j = 0;
		for( int i = n; i < l; i++ ) {
			res[i] = b[j];
			j++;
		}
		return res;
	}

	/**
	 * Special variant of concat which ignores first element of second array.
	 * Returns a(b*), the array formed by concatenating a and b* = (b1,...,bn-1)
	 * @param a
	 * @param b
	 * @return
	 */
	public static Point2d[] Concat2( Point2d[] a, Point2d[] b ) {
		int n = a.length;
		int l = n+b.length-1;
		Point2d[] res = new Point2d[l];
		for( int i = 0; i < n; i++ ) {
			res[i] = a[i];
		}
		int j = 1;
		for( int i = n; i < l; i++ ) {
			res[i] = b[j];
			j++;
		}
		return res;
	}

	/**
	 * Copies given point array and returns copy
	 * @param orig
	 * @return
	 */
	public static Point2d[] Copy( Point2d[] orig ) {
		if( orig == null )
			return null;
		Point2d[] copy = new Point2d[orig.length];
		for( int i = 0; i < orig.length; i++ ) {
			copy[i] = new Point2d( orig[i] );
		}
		return copy;
	}

	/**
	 * Returns whether given point-set actually consists of a single point.
	 * (all points are equal). If given point-set is null, false is returned.
	 * @param ps
	 * @return
	 */
	public static boolean IsOnePoint( Point2d[] ps ) {
		if( ps == null )
			return false;

		int i;
		for( i = 1; i < ps.length; i++ ) {
			if( ps[0].x.compareTo( ps[i].x ) != 0 || ps[0].y.compareTo( ps[i].y ) != 0 )
				return false;
		}
		return true;
	}

	/**
	 * sorts given n 2d-points in ascending order using given ordering-callback-function.
	 * The points are sorted in-situ in O(nlogn) time using heap-sort.
	 * @param points
	 */
	public static void SortPointsLexicographically( Point2d[] points ) {
		SortPointsLexicographically( points, points.length );
	}

	/**
	 * Sorts given n 2d-points in ascending order using given ordering-callback-function.
	 * The points are sorted in-situ in O(nlogn) time using heap-sort.
	 * @param points
	 * @param numPoints
	 */
	public static void SortPointsLexicographically( Point2d[] points, int numPoints ) {
		if( numPoints <= 1 )
			return;

		int len = numPoints;
		int half = (len>>1)-1; // first unsorted index
		int i; // indices
		Point2d temp;// temporary storage

		// first of all build min-heap from array
		for( i = half; i >= 0; i-- ) {
			MaxHeapSink( points, i, len );
		}

		// now sort heap
		// greatest element always is at heap root
		for( i = len-1; i > 0; i-- ) {
			// exchange root with point at index i and sink root
			temp = points[i];
			points[i] = points[0];
			points[0] = temp;
			MaxHeapSink( points, 0, i );
		}
	}

	/**
	 * Swaps indices of given point array:
	 * [0,1,...,n-1] -> [n-1,n-2,...,0]
	 * Running-time: O(n)
	 * @param pa
	 */
	public static void Swap( Point2d[] pa ) {
		int len = pa.length;
		if( len <= 1 )
			return;
		Point2d temp; // helper
		int i; // index;
		int half = len >> 1;
		for( i = 0; i < half; i++ ) {
			temp = pa[i];
			pa[i] = pa[len-i-1];
			pa[len-i-1] = temp;
		}
	}

	/**
	 * Converts input array to a string.
	 * The string is of the form "{(p[0].x,p[0].y);(p[1].x,p[1].y)...(p[n-1].x,p[n-1].y)}"
	 * @param arr
	 * @return string
	 */
	public static String ToArgString( Point2d[] arr ) {
		String s = "";
		if( arr.length == 0)
			return "";
		s += "{";
		int len = arr.length;
		for( int i = 0; i < len; i++ ) {
			s += "("+arr[i].x.doubleValue()+","+arr[i].y.doubleValue()+")";
			if( i < len-1 )
				s+= ";";
		}
		s += "}";
		return s;
	}
	
	//
	// PRIVATE METHODS
	//

	/**
	 * Lets ith element of given point heap sink down as long as its smaller than its childs and child-index is smaller than n
	 * @param points
	 * @param i
	 * @param n
	 */
	private static void MaxHeapSink( Point2d[] points, int i, int n ) {
		int lc, rc, ci; // left and right child index, compare index
		Point2d temp;// temporary for exchanging points
		int maxIndex = (n>>1)-1; // maximal index to compare

		while( i <= maxIndex ) {
			// get child to compare
			lc = (i<<1)+1;
			rc = lc+1;

			if( lc < n && rc < n )
				ci = Point2dOps.ComparePointsLexicographically( points[lc], points[rc] ) > 0 ? lc : rc;
			else if( lc < n )
				ci = lc;
			else
				break;

			// sink into smaller child if its greater than element at index
			if( Point2dOps.ComparePointsLexicographically( points[i], points[ci] ) < 0 ) {
				temp = points[ci];
				points[ci] = points[i];
				points[i] = temp;
				i = ci;
			}
			else
				break;
		}
	}
}
